Dynamic Programming (DP) is an algorithmic technique used to efficiently solve problems with overlapping subproblems and optimal substructure by solving each subproblem once and storing its result to avoid redundant work, using either top-down memoization or bottom-up tabulation.

Dynamic Programming is applied when:

• Optimal Substructure exists: A problem exhibits optimal substructure if an optimal solution to the problem can be constructed from optimal solutions of its subproblems.

This means that solving the whole problem can be broken into smaller problems, and solving those optimally ensures the entire problem is solved optimally.

• Overlapping Subproblems exist: A problem exhibits overlapping subproblems if it can be broken down into subproblems which are reused multiple times.

This contrasts with divide-and-conquer, where subproblems are mostly independent. In DP, subproblems repeat, making caching/memoization valuable.

Memoization - Top-Down Dynamic Programming

Memoization is an optimization technique used primarily in recursive algorithms, where the results of expensive function calls are cached and reused when the same inputs occur again. This avoid redundant computations by storing solution to subproblems as they are first computed.

 function fib(n, memo = {}){
  if(n <= 1) return n;
  if(memo[n]) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];  
 }
     
     

Tabulation - Bottom-Up Dynamic Programming

Tabulation is a technique in dynamic programming where the solution is built iteratively from the bottom up by solving all subproblems starting from the smallest and using those solutions to build up to the solution of the original problem.

   function fib(n){
    if(n <= 1) return n;
    const dp = [0, 1];
    for(let i = 2; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
   }
     
     

nth Fibonacci Number

1. Given a non negative integer n. Design an algorithm that compute and return the nth number in the Fibonacci Sequence, where the sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n is greater than or equal to 2

Ways to the Summit

2. You are Climbing, it takes n steps to reach the top. Each time you can either climb 1 or 2 steps.

Design an algorithm that returns the total number of distinct ways to reach the top.

Cheapest way to Summit

3. You are climbing a staircase. Each step has a cost.

You can start from either step 0 or step 1.

From each step, you can move one step up or skip one step (move two steps up).

Your goal is to reach the top of the staircase, which is just beyond the last step (i.e., at index n if there are n steps).

Given an array cost where cost[i] is the cost to step on the i-th stair,

Design an algorithm that computes and returns the minimum cost to reach the top.

Task Selection

4. You are given a list of daily tasks, where each task has an associated productivity score. Performing two tasks on consecutive days causes burnout, so you must skip at least one day between any two tasks you perform.

Your goal is to maximize the total productivity score without doing two consecutive tasks. Given an integer array tasks[] of length n, where tasks[i] represents the productivity score on day i,

design an efficient algorithm that returns the maximum total productivity score achievable under these conditions.

The productivity task array is provided in chronological order, where:

• tasks[0] is the productivity score of the task on Day 0 (first day)
• tasks[1] is the score on Day 1
• and so on up to tasks[n-1] (last day)

Increasing Subsequence

5. You are given an array of integers nums representing a sequence of numbers.

Design an algorithm that returns the length of the Longest Strictly Increasing Subsequences (LIS) in nums.

A subsequence is sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

The increasing subsequence must be strictly increasing (i.e., each number must be greater than the previous).

The elements do not need to be contiguous in the original array.

0/1 Knapsack Problem

1. Given n items, each with:

• a weight w[i]
• a value v[i]

You also have a knapsack that can carry at most W units of weight.

Select a subset of the items such that:

• The total weight does not exceed W.
• The total value is maximized
• Each item can be selected at most once (i.e., either included or not)

Return the maximum total value achievable under these constraints.

Minimum Coin Change

2. Given an array of positive integers coins representing denominations of currency, and an integer amount reresenting a total.

Design an algorithm that return the minimum number of coins needed to make up that amount using the denominations provided.

You may use an unlimited number of coins for each denomination.

If it is not possible to make up the amount with the given denominations, return -1.

Longest Common Subsequence

3. Given two strings text1 and text2.

Design an algorithm that compute the length of their longest common subsequence (LCS).

A subsequence of a string is a new string generated from the original string by deleting some characters (without changing the relative order of the remaining characters).

The LCS is the longest sequence that appears as a subsequence in both text1 and text2.

Return the length of this LCS.

Spell Checking

4. Given two strings word1 and word2.

Design an algorithm that compute the minimum number of operations required to convert word1 to word2.

Operations:

• Insert a character
• Delete a character
• Replace a character

Return the minimum number of operations required.

Circular Session Scheduling

5. You are organizing a circular conference schedule, where each time slot is associated with a non-negative integer value representing its potential audience interest or revenue.

Due to logistical or resource constraints, no two consecutive sessions can be scheduled, and because the schedule is circular, the first and last sessions are also considered adjacent.

Design an algorithm to determine the maximum total value that can be obtained by selecting non-consecutive time slots under these constraints.

Maximum Subarray

6. Given an array nums of integers. Design an algorithm that finds a contiguous subarray (one or more elements) that has the maximum possible sum and return the sum.

• Containing at least one element" ensures we don't return an empty subarray.
• Contiguous subarray" makes it clear that only consecutive elements count.

Unique Paths in Matrix

7. Given a grid of size m × n, where m is the number of rows and n is the number of columns. Starting from the top-left corner of the grid, you can move only right or down at each step. Your goal is to reach the bottom-right corner of the grid.

Design an algorithm that computes the total number of unique paths from the top-left to the bottom-right corner of the grid.

Equal Sum Partition

8. Given an array of positive integers.

Design an algorithm that determine whether the array can be partitioned into two subsets such that the sum of the elements in both subsets is equal.

Return True if such a partition exists, otherwise return False.

A subset is any group of elements selected from the array such that:

• The elements do not need to be contiguous.
• The order of elements does not matter.
• Each element can be used at most once.